package d_binary_search_tree.a_binary_search;

import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingTest;

import java.util.Arrays;

/**
 * 折半查找法 或 二分查找法
 * O(logn)
 * <p>
 * 只能对已排序数据进行查找
 * <p>
 * 可以参考java api - Arrays.binarySearch
 *
 * 问题: 当待查找元素在数据中有重复的时候只能找到第一个发现的目标的下标
 * 优化: 增加floor()和ceil()方法分别返回target第一次和最后一次出现的下标
 *      如果target不在数组中，那么返回排在target之前和之后的第一个元素
 */
@SuppressWarnings("unchecked")
public class BinarySearch extends SortingTest {
    @Override
    public void sort(ArrayGeneric arr) {

    }

    /**
     * 迭代实现的 二分查找
     *
     * @param arr
     * @param target
     * @return
     */
    public int binarySearchByIteration(Comparable[] arr, Comparable target) {
        // 在 arr[l..r]中进行查找
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            // int mid = (l + r) / 2; // l + r 容易造成int类型溢出，改用减法更好
            int mid = l + (r - l) / 2;
            if (arr[mid].compareTo(target) == 0) // 找到，返回下标
                return mid;
            if (arr[mid].compareTo(target) < 0) { // 向右边查找
                l = mid + 1;
            } else { // 向左查找
                r = mid - 1;
            }
        }
        return -1; // 如果不存在 返回 - 1
    }

    /**
     * 递归实现的二分查找
     *
     * 简化思路
     * 性能稍差 - 递归栈
     * @param arr
     * @param target
     * @return
     */
    public int binarySearchByRecursion(Comparable[] arr, Comparable target) {
        return binarySearchByRecursion(arr, 0, arr.length - 1, target);
    }

    private int binarySearchByRecursion(Comparable[] arr, int left, int right, Comparable target) {
        if (left > right) return -1;
        // int mid = (left + right) / 2; // 容易造成int类型溢出，改用减法更好
        int mid = left + (right - left) / 2;
        if (arr[mid].compareTo(target) == 0)
            return mid;
        if (arr[mid].compareTo(target) > 0) {
            return binarySearchByRecursion(arr, left, mid - 1, target);
        } else {
            return binarySearchByRecursion(arr, mid + 1, right, target);
        }
    }

    @Test
    public void testBinarySearchByIteration() {
        Comparable[] arr = {0, 1, 2, 3, 4, 5, 6};
        System.out.println(binarySearchByIteration(arr, 0));
        System.out.println(binarySearchByIteration(arr, 1));
        System.out.println(binarySearchByIteration(arr, 3));
        System.out.println(binarySearchByIteration(arr, 5));
        System.out.println(binarySearchByIteration(arr, 7));
    }

    @Test
    public void testBinarySearchByRecursion() {
        Comparable[] arr = {0, 1, 2, 3, 4, 5, 6};
        System.out.println(binarySearchByRecursion(arr, 0));
        System.out.println(binarySearchByRecursion(arr, 1));
        System.out.println(binarySearchByRecursion(arr, 3));
        System.out.println(binarySearchByRecursion(arr, 5));
        System.out.println(binarySearchByRecursion(arr, 7));
        // java Arrays api
        System.out.println(Arrays.binarySearch(new int[]{1, 2, 3}, 1));
        System.out.println(Arrays.binarySearch(new int[]{1, 2, 3}, 5));
    }

    /**
     * 返回arr中等于或接近target的元素的最小的位置
     * @param arr
     * @param target
     * @return
     */
    static int floor(Comparable[] arr, Comparable target){

        // 寻找比target小的最大索引
        int l = -1, r = arr.length-1;
        while( l < r ){
            // 使用向上取整避免死循环
            int mid = l + (r-l+1)/2;
            if( arr[mid].compareTo(target) >= 0 )
                r = mid - 1;
            else
                l = mid;
        }

        assert l == r;

        // 如果该索引+1就是target本身, 该索引+1即为返回值
        if( l + 1 < arr.length && arr[l+1] == target )
            return l + 1;

        // 否则, 该索引即为返回值
        return l;
    }

    /**
     * 返回arr中等于或接近target的元素的最大的位置
     * @param arr
     * @param target
     * @return
     */
    static int ceil(Comparable[] arr, Comparable target){

        // 寻找比target大的最小索引值
        int l = 0, r = arr.length;
        while( l < r ){
            // 使用普通的向下取整即可避免死循环
            int mid = l + (r-l)/2;
            if( arr[mid].compareTo(target) <= 0 )
                l = mid + 1;
            else // arr[mid] > target
                r = mid;
        }

        assert l == r;

        // 如果该索引-1就是target本身, 该索引+1即为返回值
        if( r - 1 >= 0 && arr[r-1] == target )
            return r-1;

        // 否则, 该索引即为返回值
        return r;
    }

    @Test
    public void testFloorNCeil() {
        Comparable[] arr = {1,2,3,3,3,3,3,3,3,4,6};
        System.out.println(floor(arr,3)+".." + ceil(arr,3)); //2..8
        System.out.println(floor(arr,5)+".." + ceil(arr,5)); //9//10
    }

}
